Corelab Seminar
2020-2021
Makis Arsenis
Constrained-Order Prophet Inequalities
Abstract.
Prophet inequalities bound the ratio between the expected value
obtained by two parties each selecting one value from a set of
independent random variables: a "prophet" who knows the value of
each variable and may select the maximum one, and a "gambler" who
observes the values in a particular order but must select one of them
immediately after observing it, without knowing what values will be
sampled for the unobserved variables.
In this talk we will be investigating a novel variation of the prophet
inequality setting which interpolates between two well-known extremes:
the free order and the adversarial order variant. We assume there is a
predefined set of permutations of the set indexing the random
variables, and the gambler is free to choose the order of observation
to be any one of these predefined permutations. Surprisingly, we show
that even when only two orderings are allowed (namely, the forward and
reverse orderings) the gambler-to-prophet ratio improves from 1/2 to
φ-1 = (√5 - 1) / 2 = 0.618... the inverse of the golden
ratio. As the number of allowed permutations grows beyond 2, a
striking "double plateau" phenomenon emerges: after reaching φ-1,
the gambler-to-prophet ratio achievable by uniform-threshold stopping
rules does not exceed φ-1 + o(1) until the number of allowed
permutations grows to Θ(log n). The ratio reaches 1 - 1/e - ε for a
suitably chosen set of O( poly(ε-1) log n) permutations and does
not exceed 1 - 1/e even when the full set of n! permutations is
allowed.
This talk is based on joint work with Odysseas Drosis (EPFL) and Robert
Kleinberg (Cornell) and will appear in SODA '21. The full version is available at https://arxiv.org/abs/2010.09705